package com.java.comprehensive.arithmetic.leecode.easy;

/**
 * @program: comprehensive-service
 *
 * @description: 最长公共前缀
 *
 * @author: 窦绍飞
 *
 * @create: 2021-10-29 14:02
 **/
public class LeetCode_14 {
	// leetcode submit region begin(Prohibit modification and deletion)
	static class Solution {
		public String longestCommonPrefix(String[] strs) {
			if (strs == null || strs.length == 0) {
				return "";
			}
			String prefix = strs[0];
			for (int i = 1; i < strs.length; i++) {
				prefix = Prefix(prefix, strs[i]);
				if (prefix.length() == 0) {
					break;
				}
			}
			return prefix;

		}

		public String Prefix(String s1, String s2) {
			int length = Math.min(s1.length(), s2.length());
			int index = 0;
			for (int i = 0; i < length; i++) {
				if (s1.charAt(i) != s2.charAt(i)) {
					break;
				}
				index++;
			}
			return s1.substring(0, index);
		}
	}
	static class so{
		public String longestCommonPrefix(String[] strs) {
			if ( strs.length==0 || strs==null ) {
				return "";
			}
			return divide(strs, 0, strs.length-1);

		}
		public String divide(String[] s, int left, int right) {
			if ( left==right) return s[left];
			int mid = (left+right)/2;
			String s1 = divide(s, left, mid);
			String s2 = divide(s, mid+1, right);
			return Prefix(s1, s2);

		}
		public String Prefix(String s1, String s2) {
			int length = Math.min(s1.length(), s2.length());
			int index=0;
			for ( int i=0; i<length; i++ ) {
				if ( s1.charAt(i)!= s2.charAt(i) ) {
					break;
				}
				index++;
			}
			return s1.substring(0, index);
		}

	}
	// leetcode submit region end(Prohibit modification and deletion)

	public static void main(String[] args) {
		so solution = new so();
		String strs[] = new String[] { "flower", "flow", "flight" };
		solution.longestCommonPrefix(strs);

	}
}
